This invention relates generally to the field of digital data processing apparatus and more specifically to a computer for performing a discrete Fourier transform on complex input data.
The Fourier transform has been well known to mathematicians, scientists, engineers and others for many years. The Fourier transform is a tool used in many fields such as medicine, economics, and engineering to analyze data.
For example, when the input data represents time-varying electrical signals, the Fourier transform is often performed to identify the frequency components within the electrical signals. Similarly, an inverse Fourier transform is often performed to produce a time-varying electrical signal from frequency components.
In digital data processing apparatus, the Fourier transform is normally performed with discrete values of input data in accordance with the well-known discrete Fourier transform (DFT) defined as follows: ##EQU1## The inverse Fourier transform is performed by substituting "-j" for "j" in the discrete Fourier transform. In the DFT transform, N values of the input data x(n) [where n is equal to 0, 1, . . . , (N-1)] are transformed to produce N values of output data X(k), where k is equal to 0, 1, . . . , (N-1). The number N of values of input data may vary, but the larger the value of N the greater the resolution of the output data. Transforms in accordance with the above equation are called N-point or N-length DFT's. In order to practically and efficiently perform N-length DFT's, digital computers are required. Even using digital computers, however, performance of N-length DFT's is still a formidable task. For this reason, many prior art techniques have been developed to more efficiently perform the N-length discrete Fourier transform.
One significant technique for improving the efficiency of performing the discrete Fourier transform is described in the article by J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math of Computation, Vol. 19, pp. 297-301, April 1965. When the Cooley-Tukey algorithm was utilized on a general purpose computer, a more than fifty times improvement in processing time occurred for a 1024-point DFT. The Cooley-Tukey algorithm is known as the fast Fourier transform (FFT) and is a radix-2 algorithm.
General background information concerning the fast Fourier transform (FFT) and variations thereof are described in the article "What Is The Fast Fourier Transform?", Proceedings of the IEEE, Vol. 55, No. 10, October 1967, Cochran et. al., pp. 1664-1674. The FFT method of computing the N-length DFT relies upon selecting the transform length N as a power of 2. The calculations are grouped in pairs to achieve a significant reduction in the calculation time required for the N-length DFT.
Many other algorithms have since been proposed for more efficiently performing the N-length DFT. A number of such algorithms, including the nested Winograd algorithm, are described and compared in the article "A Prime Factor FFT Algorithm Using A High-Speed Convolution" by Kolba and Parks, IEEE Transactions on Acoustics Speech and Signal Processing, Vol. ASSP-25, No. 4, August 1977, pp 281-294. In the prime factor FFT by Kolba and Parks, the transform length N is selected equal to the product of a number of mutually prime factors N.sub.1, N.sub.2, . . . , N.sub.i, . . . , N.sub.L. Each of the prime factors N.sub.i of N is employed in an N.sub.i -length DFT using convolution. In the Kolba and Parks prime factor FFT, L different and shorter-length DFT's are executed in order to achieve the N-point DFT. The Kolba and Parks prime factor FFT compares favorably with the radix-2 algorithm of Cooley-Tukey and the nested algorithm of Winograd.
While various techniques, such as those described above, have significantly improved the efficiency of performing the N-length discrete Fourier transform (DFT), even greater increases in efficiency are desirable. With this objective, special purpose computers, as distinguished from general purpose computers, have been constructed for calculating the N-length DFT. Such special purpose computers have designs which are determined to a large extent by the particular algorithm upon which they are based. In general, it is desirable that such special purpose DFT computers have a high degree of modularity. Modularity tends to reduce the manufacturing and maintenance cost of the computer. Another objective of a special purpose DFT computer is to utilize a small number of circuits again for the purpose of reducing manufacturing and maintenance costs. Another objective is to have a high execution speed. Additionally, flexibility of design is desirable so that the number of data values (N) in the transform and other parameters can be changed.
While the radix-2 FFT of Cooley-Tukey is capable of high modularity when employed in a special purpose computer, the number of circuits required is excessive and the speed of execution is not as high as desirable. While the speed of the prime factor FFT of Kolba and Parks, when implemented in a special purpose computer, is potentially greater than that of the Winograd transform or the radix-2 transform, the Kolba and Parks algorithm generally has not been susceptible of high modularity since each shorter-length prime factor DFT is of a different size. Other prior art transform techniques have similar deficiencies.
In view of the above background of the invention, there is a need for economical special purpose computers and methods for more efficiently performing N-point discrete Fourier transforms and particularly for computers which are modular and flexible in design.